The present invention relates to methods and apparatus for managing the use of a finite number of resources among a plurality of requesters, such as the processors in a multi-processor system. By way of example, the present invention has applicability in a multiprocessor system in which tokens are used to allocate resources among a plurality of requesters.
There is an apparent insatiable desire for faster computer processing data throughputs, for example, because cutting-edge computer applications involve real-time, multimedia functionality. Graphics applications are among those that place the highest demands on a processing system because they require such vast numbers of data accesses, data computations, and data manipulations in relatively short periods of time to achieve desirable visual results. These applications require extremely fast processing speeds, such as many thousands of megabits of data per second. While some processing systems employ a single processor to achieve fast processing speeds, others are implemented utilizing multi-processor architectures. In multi-processor systems, a plurality of sub-processors can operate in parallel (or at least in concert) to achieve desired processing results.
In some existing multi-processor systems, a plurality of parallel processors may compete for a finite number of resources, such as one or more shared memories, I/O interfaces, etc. Resource management techniques are employed to allocate the resources among the processors for finite periods of time in order to ensure that each processor may use the resources. The conventional approach to managing the allocation of the resources may involve an arbiter of requests for the resources.
The requesters may be the respective processors in a multi-processor and the resources may be memory banks, I/O interfaces, etc. Tokens are mechanisms used to allocate blocks of time during which the requesters may use the resources. Thus, a given resource must obtain a token before it may issue a command (load, store, move, etc.) to a bus over which the resources may be accessed. Upon initialization of the system, the requesters may be statically assigned to groups (Group 0, Group 1, Group 2, etc.) by way of operating system software (or related software) A Token Manager (TM) receives tokens from the resources and grants tokens to the requesters on a round robin priority basis. The requesters may request a token on a high/low priority basis; thus, the TM grants the tokens to the requesters on a round robin basis as to high priority token requests and on a round robin basis as to low priority token requests.
A problem with this approach of token management is that there may be a very uneven and inefficient distribution and grant of tokens to the requesters. Indeed, if a first requester in a given group often request tokens on a high priority basis for a first resource, and a second requester often request tokens on a low priority basis for the first resource, then the second requester will often have to wait for the resource. This is wasteful if another group has one or more available tokens to the first resource that are unused.